Marching Cubes算法

导读：计算机图形学作业，编程实现 Marching Cubes 算法，测试样例使用了随机数据点、以圆心按半径衰减的数据点，附带光照法线，取得了不错的效果。

原理

Marching Cubes 采用分治算法思想。它的原理是根据给出的标量场（即一堆数据点，每个空间点对应一个值，公式如下），以及一个等值面（ Isometric Surface ）阈值，经过计算后得到所求等值面，这个面能将整个三维空间划分成等值面内和等值面外两种状态。

逻辑描述如下：

if (val[xpos][ypos][zpos] < isometricValue) {
    // The point is inside the isometric surface
} else {
    // The point is outside the isometric surface
}

Marching Cubes 算法的分治体现在它以小正方体（体素，Voxel）为单位遍历整个标量场区域（本文代码中称 Voxel Container），每个小正方体的八个顶点对应标量场中的八个值，根据顶点的值是否高于预设的等值面的值，每个顶点可划分出两种状态，即高于和不高于。8个顶点将产生256种状态，这些状态对应着不同但唯一的等值面分布方式，前人经研究将其整理为三角形表（Triangular Table）描述这些状态，通过二进制状态进行编码

若体素顶点与边的编码如下：

xxxxxxxxxx
v4------e4-------v5
 |\              | \
 | e7            |  e5
 e8  \           e9   \
 |   v7------e6--|----v6
 |    |          |     |
v0----|-e0------v1     |
  \   e11         \    e10
   e3 |            e1  |
    \ |              \ |
     v3 ------e2------v2

假设 v4，v6，v2 三点的值比等值面高，则这三个点在等值面外。

为了验证等值面的分布，首先通过二进制编码计算其三角形表查找索引：

xxxxxxxxxx
+-------+-----+-----+-----+-----+-----+-----+-----+-----+
|  Pos  |  7  |  6  |  5  |  4  |  3  |  2  |  1  |  0  |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+
|  SW   |  0  |  1  |  0  |  1  |  0  |  1  |  0  |  0  |
+-------+-----+-----+-----+-----+-----+-----+-----+-----+

根据二进制转十进制方式计算索引，得 2 ^ 6 + 2 ^ 4 + 2 ^ 2 = 52

查找三角形表，得52对应的三角形分布应为：

xxxxxxxxxx
9,7,8,9,5,7,10,1,2,-1,-1,-1,-1,-1,-1,-1